An integrated circuit (IC) comprises cells of similar and/or various sizes, and connections between or among the cells. A cell includes several pins interconnected by wires to pins of one or more other cells. A net includes a set of pins connected by wires in order to form connections between or among the pins. A set of nets, called a netlist, defines the connections of an IC. In other words, a netlist specifies a group of nets, which, in turn, specify the interconnections between a set of pins.
Design engineers design IC's by transforming circuit descriptions of the IC's into geometric descriptions, called layouts. To create layouts, design engineers typically use electronic design automation (EDA) applications. These applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts.
EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectilinear lines to represent the wire segments that interconnect the IC components. These tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes.
The IC design process entails various operations. Some of the physical-design operations that EDA applications commonly perform to obtain the IC layouts are: (1) circuit partitioning, which partitions a circuit if the circuit is too large for a single chip; (2) floor planning, which finds the alignment and relative orientation of the circuit modules; (3) placement, which determines more precisely the positions of the circuit components; (4) routing, which completes the interconnects between or among the circuit components; and (5) verification, which checks the layout to ensure that it meets design and functional requirements.
Routing is a key operation in the physical design cycle. It is generally divided into two phases: global routing and detailed routing. For each net, global routing generates a routing topology that includes an approximate route for the interconnect lines that are to connect the pins of the net. After the routing topology has been created, detailed routing creates specific individual routing paths for each net.
Traditional routing algorithms adopt a flat framework that finds paths for nets in the whole routing region directly. The Steiner-tree approach is an example of a traditional routing algorithm. With the Steiner-tree approach, a minimum rectilinear Steiner tree (MRST) is used for routing a multi-pin net with minimum wire length. Given m points in the plane, an MRST connects all points by rectilinear lines, possibly via some extra points (called Steiner points), to achieve a minimum-wire-length tree of rectilinear edges. Although the Steiner-tree approach generates routing topologies that are optimized for wire length (e.g., in which routing paths use the minimum possible wire length), the Steiner-tree approach does not optimize the distance from source to sink. Thus, the Steiner-tree approach fails to address potential time delay issues that may be caused by excessive distances between source and sink, and as a result, the performance of the resulting IC may suffer.
Further, due to the large number of nets in the netlist, it typically takes a long time for conventional routers to finish the connection task. In addition, the connections may be too numerous and/or overcrowded, such that conventional routers fail to finish the routing, particularly generating interconnections, without creating one or more design rule violations.